package com.wwy.arithmetic.suanfa;

import com.wwy.arithmetic.suanfa.entry.TreeNode;
import sun.reflect.generics.tree.Tree;

import javax.validation.constraints.Max;
import java.util.Arrays;

/**
 * 给定一个数组，判断其是否是平衡二叉树
 */
public class PanDuanPingHeng {

    public static void main(String[] args) {
        TreeNode treeNode = new TreeNode();
        treeNode.setVal(3);
        TreeNode treeNode1 = new TreeNode();
        treeNode1.setVal(1);
        TreeNode treeNode2 = new TreeNode();
        treeNode2.setVal(2);
        TreeNode treeNode3 = new TreeNode();
        treeNode3.setVal(3);
        TreeNode treeNode4 = new TreeNode();
        treeNode4.setVal(4);
        TreeNode treeNode5 = new TreeNode();
        treeNode5.setVal(5);

        treeNode.setLeft(treeNode1);
        treeNode.setRight(treeNode2);
        treeNode1.setLeft(treeNode3);
        treeNode1.setRight(treeNode4);
        treeNode3.setLeft(treeNode5);
        boolean balanced = isBalanced(treeNode);
        System.out.println("balanced = " + balanced);
    }

//    public static boolean isBalanced(TreeNode root) {
//        if (root == null) {
//            return true;
//        } else {
//            return Math.abs(height(root.getLeft()) - height(root.getRight())) <= 1 && isBalanced(root.getLeft()) && isBalanced(root.getRight());
//        }
//    }
//
//    public static int height(TreeNode root) {
//        if (root == null) {
//            return 0;
//        } else {
//            return Math.max(height(root.getLeft()), height(root.getRight())) + 1;
//        }
//    }


    static boolean judge(TreeNode root) {
        if (root == null) {
            return true;
        } else {
            if (Math.abs(getDifferenceValue(root.getLeft()) - getDifferenceValue(root.getRight())) <= 1 && judge(root.getRight()) && judge(root.getLeft())) {
                return true;
            } else {
                return false;
            }
        }
    }

    static int getDifferenceValue(TreeNode left) {
        if (left == null) {
            return 0;
        } else {
            return Math.max(getDifferenceValue(left.getLeft()), getDifferenceValue(left.getRight())) + 1;
        }
    }

    public static boolean isBalanced(TreeNode root) {
        return height(root) >= 0;
    }

    public static int height(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftHeight = height(root.getLeft());
        int rightHeight = height(root.getRight());
        if (leftHeight == -1 || rightHeight == -1 || Math.abs(leftHeight - rightHeight) > 1) {
            return -1;
        } else {
            return Math.max(leftHeight, rightHeight) + 1;
        }
    }


}
